D - 禁止された数字
A~Bまでの整数の中で、数字の中に4または9が含まれているものは何個あるか。
桁DPの入門にいい感じの問題。因みに自分は人のやつを写しながら理解しました。難しくないか（初見には）
まずこの「AからBまでの〇〇の値」というのは、0~Bまでの答えから0~A-1の値を引けば求まります。つまり作る必要があるのは、0~Nまでで数えるみたいな関数。
値の持ち方
桁DPはNをstringでもつことが多い。普通に持とうとするとオーバーフローするので。
今回は最大$ 10^{18}なので、long longに入れることができる。
関数にstringで渡してもいいけど、今回はllで渡して関数内でstringに変換した(自分は)。
stringで渡す時は、「const string &s」で渡すように。参照にすることでコピーが減るのでよい constは付けたほうがいい…
(普通に渡してしまうと一旦別のアドレスにコピーされるので、それだけ時間がかかる)
dp[32][2][2] // dp[i桁目まで確定した時][既にn未満確定?][4か9が出てきたか?]みたいなDPテーブルを作ります。
code:sample.cpp
ll solve(ll n) {
string s = to_string(n);
fill((ll *)dp, (ll *)dp + sizeof(dp) / sizeof(ll), 0);
// for文使ってループする
REP(i, s.size()) {
int D = si - '0'; // 今見ている桁の値 REP(j, 2)
REP(k, 2)
REP(d, j ? 10 : D + 1)
}
}
中身はこんな感じにした。